package qsc.algorithm.sort.quickSort;

    /**
     * @auther QiuShangcheng
     * @create 2021/5/12
     */
    public class QuickSort {
        public static void quickSort(int[] arr, int left, int right) {
            int l = left; //左下标
            int r = right; //右下标
            //pivot 中轴值
            int pivot = arr[(left + right) / 2];
            while (l < r) {
                //在pivot的左边一直找,找到大于等于pivot值,才退出
                while (arr[l] < pivot) {
                    l++;
                }
                //在pivot的右边一直找,找到小于等于pivot值,才退出
                while (arr[r] > pivot) {
                    r--;
                }
                //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
                //小于等于pivot值，右边全部是大于等于pivot值
                if (l >= r) {
                    break;
                }
                //交换
                int temp;
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                //左边右移，右边左移，避免死循环
                r--;
                l++;
            }
            // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
            if (l == r) {
                l++;
                r--;
            }
            //向左递归
            if (left < r) {
                quickSort(arr, left, r);
            }
            //向右递归
            if (right > l) {
                quickSort(arr, l, right);
            }
        }
    }
